#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ArrayLen 10
int arraySize;

int HeapSize(int op_array[])
{
	return arraySize;
}


/*
PARENT(i)
return __i/2__ // int i = i/2;

LEFT(i)
return 2i

RIGHT(i)
return 2i + 1
*/
int Parent(int i)
{
	if(i==0)
		return 0;
	return (i+1)/2 - 1;
}

int Left(int i)
{
	return 2*(i+1) - 1;
}

int Right(int i)
{
	return 2*(i+1);
}

void exchange(int *a,int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void MaxHeapify(int op_array[],int i)
{
	int l = Left(i);
	int r = Right(i);

	int largest=i;

	if(l<HeapSize(op_array) && op_array[l]>op_array[i])
		largest = l;

	if(r<HeapSize(op_array)&& op_array[r]>op_array[largest])
		largest = r;

	if(largest!=i)
	{
		exchange(&op_array[i],&op_array[largest]);
		MaxHeapify(op_array,largest);
	}
}


void Generate_Array(int op_array[]) 
{
	
}

void Build_Max_Heap(int op_array[])
{
	int i=0;
	for(i=ArrayLen/2-1;i>=0;i--)
		MaxHeapify(op_array,i);
}

int main() 
{ 
	arraySize = ArrayLen;
	int op_array[ArrayLen] = {3,5,7,1,3,12,56,8,7,16};
	int i;
	Generate_Array(op_array);

	printf("Heap Tree Test\n");
	printf("Heap Size %d\n",HeapSize(op_array));
	//exchange(&op_array[1],&op_array[2]); op_array Test
	//for(i=ArrayLen/2-1;i>=0;i--)
	//	MaxHeapify(op_array,i);


	Build_Max_Heap(op_array);

	for(i=ArrayLen-1;i>=1;i--)
	{
		exchange(&op_array[0],&op_array[i]);
		arraySize--;
		MaxHeapify(op_array,0);
	}

	for(i=0;i<ArrayLen;i++)
		printf("%d\t",op_array[i]);

	printf("\n");
	return 0; 
} 
